//顺序表（动态顺序链表）
#ifndef __SEQUENTIALLIST__HPP
#define __SEQUENTIALLIST__HPP

#include"VirtualLinkedList.hpp"

namespace NgSiuKei {

template<class TheClass>
class SequentialList: public VirtualLinkedList<TheClass> {
    public:
    SequentialList(void);
    ~SequentialList(void);

    public:
    //清空
    void clear(void);
    //获取特定下标的元素值
    TheClass getVal(const U_L_L &index) const;
    //查找数据，返回下标，表没有则抛出异常：EXCEPTION_CAN_NOT_FIND
    U_L_L findVal(const TheClass &val) const;
    //插入数据
    void insertVal(const TheClass &val, const U_L_L &index);
    //删除特定下标的元素，返回元素值
    TheClass deleteWithIndex(const U_L_L &index);
    //打印表
    void print(void);

    private:
    TheClass * p;
    U_L_L maxSize;
};

template<class TheClass>
SequentialList<TheClass>::SequentialList(void): VirtualLinkedList<TheClass>() {
    this->maxSize = MAX_SIZE;
    this->p = new TheClass[this->maxSize];
}

template<class TheClass>
SequentialList<TheClass>::~SequentialList(void) {
    if(nullptr != this->p) {
        delete this->p;
        this->p = nullptr;
    }
}

template<class TheClass>
void SequentialList<TheClass>::clear(void) {
    this->size = 0;//不用清空数组，多此一举，size就是表大小唯一标识，即使数组有数据
}

template<class TheClass>
TheClass SequentialList<TheClass>::getVal(const U_L_L &index) const {
    if(this->isEmpty()) {
        throw EXCEPTION_IS_EMPTY;
    }
    if(index>=this->size) {
        throw EXCEPTION_OUT_OF_BOUNDS;
    }
    return this->p[index];
}

template<class TheClass>
U_L_L SequentialList<TheClass>::findVal(const TheClass &val) const {
    if(this->isEmpty()) {
        EXCEPTION_IS_EMPTY;
    }
    for(U_L_L i = 0; i<this->size; ++i) {
        if(this->p[i] == val) {
            return i;
        }
    }
    throw EXCEPTION_CAN_NOT_FIND;
}

template<class TheClass>
void SequentialList<TheClass>::insertVal(const TheClass &val, const U_L_L &index) {
    if(index > this->size) {
        throw EXCEPTION_OUT_OF_BOUNDS;
    }
    if(this->size == this->maxSize) {//当表大小等于容量大小时，需要扩容
        ++this->size;
        this->maxSize += MAX_SIZE;
        TheClass *temp = this->p;
        this->p = new TheClass[this->maxSize];
        for(U_L_L i=0; i<this->size; ++i) {
            if(i<index) {
                this->p[i] = temp[i];
            }
            else if(i == index) {
                this->p[i] = val;
            }
            else {
                this->p[i] = temp[i-1];
            }
        }
        delete temp;
    }
    else {
        for(U_L_L i=this->size; i>index; --i) {
            this->p[i] = this->p[i-1];
        }
        this->p[index] = val;
        ++this->size;
    }
}

template<class TheClass>
TheClass SequentialList<TheClass>::deleteWithIndex(const U_L_L &index) {
    if(this->isEmpty()) {
        throw EXCEPTION_IS_EMPTY;
    }
    if(index >= this->size) {
        throw EXCEPTION_OUT_OF_BOUNDS;
    }
    this->size--;
    TheClass result = this->p[index];
    for(U_L_L i=index; i<this->size; ++i) {
        this->p[i] = this->p[i+1];
    }
    return result;
}

template<class TheClass>
void SequentialList<TheClass>::print(void) {
    cout << "打印顺序表：[ ";
    for(U_L_L i=0; i<this->size; ++i) {
        cout << this->p[i] << ' ';
    }
    cout << ']' << endl;
}

}

#endif